/*
hamming.cpp:	a C++ version for calculating hamming numbers, aka regular numbers, 
                aka ugly numbers, in compile time (using template meta programming).
    Copyright (C) 2008  Daniel Gutson
    
    hamming.cpp is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License as
    published by the Free Software Foundation, either version 3 of the
    License, or (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

    This program computes the n-th iteration of the Dijkstra algorithm
    provide in Wikipedia.
    
    For questions, contact me: danielgutson@gmail.com, or visit my
    homepage at http://danielgutson.googlepages.com/professionalinformation
*/

#include <iostream>
using namespace std;


struct NIL{};

template <int H, class T>
struct List
{
    enum { HEAD = H};
    typedef T TAIL;
};

enum COMP_TYPE
{
    kEQ,
    kLESS,
    kMORE
};

template <int A, int B>
struct COMP
{
    enum { val = ( A == B ? kEQ : ( A < B ? kLESS : kMORE ) ) };
};

template <class L>
struct PRINTL
{
    static void print() { cout << L::HEAD << " "; PRINTL<typename L::TAIL>::print(); }
};

template <>
struct PRINTL<NIL>
{
    static void print() { cout << endl; }
};


typedef List<1,NIL> START;




template <class L, int MUL>
struct GROW
{
    typedef List<L::HEAD * MUL, typename GROW<typename L::TAIL, MUL>::RET > RET;
};

template <int MUL>
struct GROW<NIL, MUL>
{
    typedef NIL RET;
};


template <class L1, class L2, int L1_L2> struct MERGE2_;

template <class L1, class L2>
struct MERGE2
{
    typedef typename MERGE2_<L1, L2, COMP<L1::HEAD, L2::HEAD>::val >::RET RET;
};

template <class L>
struct MERGE2<L, NIL>
{
    typedef L RET;
};

template <class L>
struct MERGE2<NIL,L>
{
    typedef L RET;
};


template <class L1, class L2, int L1_L2>	// assume EQ
struct MERGE2_
{
    typedef List<L1::HEAD, typename MERGE2<typename L1::TAIL, typename L2::TAIL>::RET > RET;
};

template <class L1, class L2>
struct MERGE2_<L1, L2, kLESS>	// L1::HEAD < L2::HEAD
{
    typedef List<L1::HEAD, typename MERGE2<typename L1::TAIL, L2>::RET > RET;
};

template <class L1, class L2>
struct MERGE2_<L1, L2, kMORE>	// L1::HEAD > L2::HEAD
{
    typedef List<L2::HEAD, typename MERGE2<L1, typename L2::TAIL>::RET > RET;
};

template <class L, int IT>
struct HAMMING
{
    typedef typename
	    HAMMING<
		typename MERGE2<
		    typename MERGE2< L, typename GROW<L, 2>::RET >::RET,
		    typename MERGE2< typename GROW<L, 3>::RET, typename GROW<L, 5>::RET>::RET
		>::RET,
	    IT-1>::RET RET;
};

template <class L>
struct HAMMING<L, 0>
{
    typedef L RET;
};




int main()
{
    PRINTL<HAMMING<START, 5>::RET >::print();
}
